package com.leecode.xiehf.page_21;

import com.leecode.Printer;

public class Solution_1011 extends Printer {
    public static void main(String[] args) {
        Solution_1011 solution = new Solution_1011();
        int i = solution.shipWithinDays(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5);
        print(i);
    }

    /**
     * 结果必然是处于 「max，sum」之间
     * @param weights
     * @param D
     * @return
     */
    public int shipWithinDays(int[] weights, int D) {
        if (weights==null || weights.length == 0) {
            return 0;
        }
        int sum = 0;
        int max = weights[0];
        for(int num: weights) {
            sum += num;
            if (num > max) {
                max = num;
            }
        }
        int left = max;
        int right = sum;
        while (left < right) {
            int mid = (left + right) / 2;
            int need = 1, cur = 0;
            for (int num : weights) {
                if (cur + num > mid) {
                    ++need;
                    cur = 0;
                }
                cur += num;
            }
            if (need <= D) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
